package LeetCode刷题;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-11 15:58
 * @description: Functions of this class is
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 *
 * 官方解题法：（迭代）
 * class Solution {
 *   public int kthSmallest(TreeNode root, int k) {
 *     LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
 *
 *     while (true) {
 *       while (root != null) {
 *         stack.add(root);
 *         root = root.left;
 *       }
 *       root = stack.removeLast();
 *       if (--k == 0) return root.val;
 *       root = root.right;
 *     }
 *   }
 * }
 * 时间复杂度：O(H + k)，其中 H 指的是树的高度，由于我们开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为O(logN+k)。
 * 当树是一个不平衡树时：复杂度为 O(N+k)，此时所有的节点都在左子树。
 * 空间复杂度：O(H + k)。当树是一个平衡树时：O(logN + k)。当树是一个非平衡树时：O}(N + k)。
 *
 **/
public class 二叉搜索树中第k小的元素 {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public static void main(String arg[]){
        TreeNode treeNode1=new TreeNode();
        TreeNode treeNode2=new TreeNode();
        TreeNode treeNode3=new TreeNode();
        TreeNode treeNode4=new TreeNode();

        treeNode3.val=1;
        treeNode1.val=1;
        treeNode2.val=2;
        treeNode4.val=4;

        treeNode3.left=treeNode1;
        treeNode3.right=treeNode4;
        treeNode1.right=treeNode2;

        System.out.println(kthSmallest(treeNode3,3));
    }
    public static int kthSmallest(TreeNode root, int k) {
        k--;
        List<Integer> nums=new ArrayList();
        inOrder(root,nums);
        nums.stream().sorted();
        return nums.get(k);
    }
    private static void inOrder(TreeNode root,List<Integer>nums){
        if(root!=null){
            inOrder(root.left,nums);
            nums.add(root.val);
            inOrder(root.right,nums);
        }
    }
}